package com.dateConstruction._02_sortedSeqList;

import com.dateConstruction._02_seqList.SeqList;

// 排序顺序表（升序）类，继承顺序类
// T或T的某个祖先类"?"实现Comparable<?>接口,提供compareTo()方法比较对象大小和相等

public class SortedSeqList<T extends Comparable<? super T>> extends SeqList<T> {
    
    // 构造空排序顺序表
    public SortedSeqList() {
        // 默认调用父类构造方法SeqList()
        super();
    }
    
    // 构造空排序顺序表，容量为length
    public SortedSeqList(int length) {
        // 调用SeqList(length)
        super(length);
    }
    
    // 构造排序顺序表，由数组提供元素
    public SortedSeqList(T[] values) {
        // 调用SeqList(length)
        super(values.length);
        for (int i = 0; i < values.length; i++) {
            this.insert(values[i]);
        }
    }
    
    // 不支持父类的以下成员方法，将其覆盖并抛出异常
    // 排序顺序表的数据元素具有只读特性，不支持写操作
    public void set(int i, T x) {
        throw new UnsupportedOperationException("set(int i, T x)");
    }
    
    // 不支持在指定位置插入
    public int insert(int i ,T x) {
        throw new UnsupportedOperationException("insert(int i, T x)");
    }
    
    // 插入x，x != null，根据x对象大小顺序查找确定插入位置（升序），插入在等值元素之后，返回x序号
    // 调用T的compareTo()方法比较对象大小，覆盖父类insert(x)，参数列表和返回值相同
    public int insert(T x) {
        int i = 0;
        // compareTo()比较大小，顺序表为空，或大于表中最后一个元素
        if (this.isEmpty() || x.compareTo(this.get(this.n-1)) > 0) {
            i = this.n;
        } else {
            while (i < this.n && x.compareTo(this.get(i)) >= 0) {
                i++;
            }
        }
        super.insert(i, x);
        return i;
    }
    
    // 顺序查找与key相等的元素，由key的compareTo()方法确定元素的大小和相等
    // 返回元素序号i(0 <= i < n)，若查找不成功，则返回-1，O(n)，覆盖
    public int search(T key) {
        for (int i = 0; i < this.n && key.compareTo(this.get(i)) >= 0; i++) {
            if (key.compareTo(this.get(i)) == 0) {
                return i;
            }
        }
        return -1;
    }
    
    // 删除顺序查找并删除首个与key相等的元素，返回被删除的元素；若查找不成功，则返回null
    // 先查找，再调用remove(i)，若查找不成功，则返回-1，不删除且返回null
    public T remove(T key) {
        return remove(search(key));
    }
    
    // 拷贝构造方法，深拷贝
    public SortedSeqList(SortedSeqList<? extends T> slist) {
        // 调用SeqList(SeqList<T> list)，参数SeqList<T> list = slist赋值相容，list引用子类实例
        super(slist);
    }
    
    // 由顺序表slist构造排序顺序表this，深拷贝，O(n^2)；slist可引用子类实例
    // 参数类型SeqList<T>中的T，是SortedSeqList<T>类声明的T，可比较大小
    public SortedSeqList(SeqList<? extends T> slist) {
        for (int i = 0; i < slist.size(); i++) {
            this.insert(slist.get(i));
        }
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        System.out.println("测试(T[])构造方法:");
        Integer[] values = {3, 2, 6, 4, 5, 1};
        SortedSeqList<Integer> sslist1 = new SortedSeqList<Integer>(values);
        System.out.println(sslist1);
        System.out.println("测试search(T)和remove(T)方法：");
        // 这里让T为Integer来测试，sslist1.remove(6)调用的是父类删除指定索引元素的方法
        System.out.println(sslist1.search(6) + ", " + sslist1.remove((Integer)6));
        System.out.println("测试深拷贝构造方法：");
        SortedSeqList<Integer> sslist2 = new SortedSeqList<Integer>(sslist1);
        System.out.println(sslist2);
        sslist1.remove((Integer)5);
        System.out.println(sslist1 + ", " + sslist2);
        System.out.println("测试排序深拷贝构造方法：");
        SeqList<Integer> slist3 = new SeqList<Integer>(values);
        System.out.println(slist3);
        SortedSeqList<Integer> sslist3 = new SortedSeqList<Integer>(slist3);
        System.out.println(sslist3);
    }

}
